#include <cstdio>

char s[ 200001 ];
int next[ 200001 ], f[ 200001 ];

void getnext( char *s, int *next )
{
    int i = 1, j = -1;
    next[ 0 ] = -1;
    while ( s[ i ] )
    {
        while ( j >= 0 && s[ j + 1 ] != s[ i ] ) j = next[ j ];
        if ( s[ j + 1 ] == s[ i ] ) j++;
        next[ i++ ] = j;
    }
}

int main( )
{
    int t, n, i, sum;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d%s", &n, s);
        getnext( s, next );
        f[ 0 ] = 1;
        for ( i = 1; i < n; i++ )
            if ( next[ i ] == -1 )
                f[ i ] = 1;
            else
                f[ i ] = ( f[ next[ i ] ] + 1 ) % 10007;
        sum = 0;
        for ( i = 0; i < n; i++ )
            sum = ( sum + f[ i ] ) % 10007;
        printf("%d\n", sum);
    }
    return 0;
}
